// PART OF THE MACHINE SIMULATION. DO NOT CHANGE.

package nachos.machine;

import nachos.security.*;
import nachos.threads.KThread;

import java.util.Vector;

/**
 * A TCB simulates the low-level details necessary to create, context-switch,
 * and destroy Nachos threads. Each TCB controls an underlying JVM Thread
 * object.
 * 
 * <p>
 * Do not use any methods in <tt>java.lang.Thread</tt>, as they are not
 * compatible with the TCB API. Most <tt>Thread</tt> methods will either crash
 * Nachos or have no useful effect.
 * 
 * <p>
 * Do not use the <i>synchronized</i> keyword <b>anywhere</b> in your code. It's
 * against the rules, <i>and</i> it can easily deadlock nachos.
 */
public final class TCB {
	/**
	 * Allocate a new TCB.
	 */
	public TCB() {
	}

	/**
	 * Give the TCB class the necessary privilege to create threads. This is
	 * necessary, because unlike other machine classes that need privilege, we
	 * want the kernel to be able to create TCB objects on its own.
	 * 
	 * @param privilege
	 *            encapsulates privileged access to the Nachos machine.
	 */
	public static void givePrivilege(Privilege privilege) {
		TCB.privilege = privilege;
		privilege.tcb = new TCBPrivilege();
	}

	/**
	 * Causes the thread represented by this TCB to begin execution. The
	 * specified target is run in the thread.
	 */
	public void start(Runnable target) {
		/*
		 * We will not use synchronization here, because we're assuming that
		 * either this is the first call to start(), or we're being called in
		 * the context of another TCB. Since we only allow one TCB to run at a
		 * time, no synchronization is necessary.
		 * 
		 * The only way this assumption could be broken is if one of our
		 * non-Nachos threads used the TCB code.
		 */

		/*
		 * Make sure this TCB has not already been started. If done is false,
		 * then destroy() has not yet set javaThread back to null, so we can use
		 * javaThread as a reliable indicator of whether or not start() has
		 * already been invoked.
		 */
		Lib.assertTrue(javaThread == null && !done);

		/*
		 * Make sure there aren't too many running TCBs already. This limitation
		 * exists in an effort to prevent wild thread usage.
		 */
		Lib.assertTrue(runningThreads.size() < maxThreads);

		isFirstTCB = (currentTCB == null);

		/*
		 * Probably unnecessary sanity check: if this is not the first TCB, we
		 * make sure that the current thread is bound to the current TCB. This
		 * check can only fail if non-Nachos threads invoke start().
		 */
		if (!isFirstTCB)
			Lib.assertTrue(currentTCB.javaThread == Thread.currentThread());

		/*
		 * At this point all checks are complete, so we go ahead and start the
		 * TCB. Whether or not this is the first TCB, it gets added to
		 * runningThreads, and we save the target closure.
		 */
		runningThreads.add(this);

		this.target = target;

		if (!isFirstTCB) {
			/*
			 * If this is not the first TCB, we have to make a new Java thread
			 * to run it. Creating Java threads is a privileged operation.
			 */
			tcbTarget = new Runnable() {
				public void run() {
					threadroot();
				}
			};

			privilege.doPrivileged(new Runnable() {
				public void run() {
					javaThread = new Thread(tcbTarget);
				}
			});

			/*
			 * The Java thread hasn't yet started, but we need to get it
			 * blocking in yield(). We do this by temporarily turning off the
			 * current TCB, starting the new Java thread, and waiting for it to
			 * wake us up from threadroot(). Once the new TCB wakes us up, it's
			 * safe to context switch to the new TCB.
			 */
			currentTCB.running = false;

			this.javaThread.start();
			currentTCB.waitForInterrupt();
		} else {
			/*
			 * This is the first TCB, so we don't need to make a new Java thread
			 * to run it; we just steal the current Java thread.
			 */
			javaThread = Thread.currentThread();

			/* All we have to do now is invoke threadroot() directly. */
			threadroot();
		}
	}

	/**
	 * Return the TCB of the currently running thread.
	 */
	public static TCB currentTCB() {
		return currentTCB;
	}

	/**
	 * Context switch between the current TCB and this TCB. This TCB will become
	 * the new current TCB. It is acceptable for this TCB to be the current TCB.
	 */
	public void contextSwitch() {
		/*
		 * Probably unnecessary sanity check: we make sure that the current
		 * thread is bound to the current TCB. This check can only fail if
		 * non-Nachos threads invoke start().
		 */
		Lib.assertTrue(currentTCB.javaThread == Thread.currentThread());

		// make sure AutoGrader.runningThread() called associateThread()
		Lib.assertTrue(currentTCB.associated);
		currentTCB.associated = false;

		// can't switch from a TCB to itself
		if (this == currentTCB)
			return;

		/*
		 * There are some synchronization concerns here. As soon as we wake up
		 * the next thread, we cannot assume anything about static variables, or
		 * about any TCB's state. Therefore, before waking up the next thread,
		 * we must latch the value of currentTCB, and set its running flag to
		 * false (so that, in case we get interrupted before we call yield(),
		 * the interrupt will set the running flag and yield() won't block).
		 */

		TCB previous = currentTCB;
		previous.running = false;

		this.interrupt();
		previous.yield();
	}

	/**
	 * Destroy this TCB. This TCB must not be in use by the current thread. This
	 * TCB must also have been authorized to be destroyed by the autograder.
	 */
	public void destroy() {
		// make sure the current TCB is correct
		Lib.assertTrue(currentTCB != null
				&& currentTCB.javaThread == Thread.currentThread());
		// can't destroy current thread
		Lib.assertTrue(this != currentTCB);
		// thread must have started but not be destroyed yet
		Lib.assertTrue(javaThread != null && !done);

		// ensure AutoGrader.finishingCurrentThread() called authorizeDestroy()
		Lib.assertTrue(nachosThread == toBeDestroyed);
		toBeDestroyed = null;

		this.done = true;
		currentTCB.running = false;

		this.interrupt();
		currentTCB.waitForInterrupt();

		this.javaThread = null;
	}

	/**
	 * Destroy all TCBs and exit Nachos. Same as <tt>Machine.terminate()</tt>.
	 */
	public static void die() {
		privilege.exit(0);
	}

	/**
	 * Test if the current JVM thread belongs to a Nachos TCB. The AWT event
	 * dispatcher is an example of a non-Nachos thread.
	 * 
	 * @return <tt>true</tt> if the current JVM thread is a Nachos thread.
	 */
	public static boolean isNachosThread() {
		return (currentTCB != null && Thread.currentThread() == currentTCB.javaThread);
	}

	private void threadroot() {
		// this should be running the current thread
		Lib.assertTrue(javaThread == Thread.currentThread());

		if (!isFirstTCB) {
			/*
			 * start() is waiting for us to wake it up, signalling that it's OK
			 * to context switch to us. We leave the running flag false so that
			 * we'll still run if a context switch happens before we go to
			 * sleep. All we have to do is wake up the current TCB and then wait
			 * to get woken up by contextSwitch() or destroy().
			 */

			currentTCB.interrupt();
			this.yield();
		} else {
			/*
			 * start() called us directly, so we just need to initialize a
			 * couple things.
			 */

			currentTCB = this;
			running = true;
		}

		try {
			target.run();

			// no way out of here without going throw one of the catch blocks
			Lib.assertNotReached();
		} catch (ThreadDeath e) {
			// make sure this TCB is being destroyed properly
			if (!done) {
				System.out.print("\nTCB terminated improperly!\n");
				privilege.exit(1);
			}

			runningThreads.removeElement(this);
			if (runningThreads.isEmpty())
				privilege.exit(0);
		} catch (Throwable e) {
			System.out.print("\n");
			e.printStackTrace();

			runningThreads.removeElement(this);
			if (runningThreads.isEmpty())
				privilege.exit(1);
			else
				die();
		}
	}

	/**
	 * Invoked by threadroot() and by contextSwitch() when it is necessary to
	 * wait for another TCB to context switch to this TCB. Since this TCB might
	 * get destroyed instead, we check the <tt>done</tt> flag after waking up.
	 * If it is set, the TCB that woke us up is waiting for an acknowledgement
	 * in destroy(). Otherwise, we just set the current TCB to this TCB and
	 * return.
	 */
	private void yield() {
		waitForInterrupt();

		if (done) {
			currentTCB.interrupt();
			throw new ThreadDeath();
		}

		currentTCB = this;
	}

	/**
	 * Waits on the monitor bound to this TCB until its <tt>running</tt> flag is
	 * set to <tt>true</tt>. <tt>waitForInterrupt()</tt> is used whenever a TCB
	 * needs to go to wait for its turn to run. This includes the ping-pong
	 * process of starting and destroying TCBs, as well as in context switching
	 * from this TCB to another. We don't rely on <tt>currentTCB</tt>, since it
	 * is updated by <tt>contextSwitch()</tt> before we get called.
	 */
	private synchronized void waitForInterrupt() {
		while (!running) {
			try {
				wait();
			} catch (InterruptedException e) {
			}
		}
	}

	/**
	 * Wake up this TCB by setting its <tt>running</tt> flag to <tt>true</tt>
	 * and signalling the monitor bound to it. Used in the ping-pong process of
	 * starting and destroying TCBs, as well as in context switching to this
	 * TCB.
	 */
	private synchronized void interrupt() {
		running = true;
		notify();
	}

	private void associateThread(KThread thread) {
		// make sure AutoGrader.runningThread() gets called only once per
		// context switch
		Lib.assertTrue(!associated);
		associated = true;

		Lib.assertTrue(thread != null);

		if (nachosThread != null)
			Lib.assertTrue(thread == nachosThread);
		else
			nachosThread = thread;
	}

	private static void authorizeDestroy(KThread thread) {
		// make sure AutoGrader.finishingThread() gets called only once per
		// destroy
		Lib.assertTrue(toBeDestroyed == null);
		toBeDestroyed = thread;
	}

	/**
	 * The maximum number of started, non-destroyed TCB's that can be in
	 * existence.
	 */
	public static final int maxThreads = 250;

	/**
	 * A reference to the currently running TCB. It is initialized to
	 * <tt>null</tt> when the <tt>TCB</tt> class is loaded, and then the first
	 * invocation of <tt>start(Runnable)</tt> assigns <tt>currentTCB</tt> a
	 * reference to the first TCB. After that, only <tt>yield()</tt> can change
	 * <tt>currentTCB</tt> to the current TCB, and only after
	 * <tt>waitForInterrupt()</tt> returns.
	 * 
	 * <p>
	 * Note that <tt>currentTCB.javaThread</tt> will not be the current thread
	 * if the current thread is not bound to a TCB (this includes the threads
	 * created for the hardware simulation).
	 */
	private static TCB currentTCB = null;

	/**
	 * A vector containing all <i>running</i> TCB objects. It is initialized to
	 * an empty vector when the <tt>TCB</tt> class is loaded. TCB objects are
	 * added only in <tt>start(Runnable)</tt>, which can only be invoked once on
	 * each TCB object. TCB objects are removed only in each of the
	 * <tt>catch</tt> clauses of <tt>threadroot()</tt>, one of which is always
	 * invoked on thread termination. The maximum number of threads in
	 * <tt>runningThreads</tt> is limited to <tt>maxThreads</tt> by
	 * <tt>start(Runnable)</tt>. If <tt>threadroot()</tt> drops the number of
	 * TCB objects in <tt>runningThreads</tt> to zero, Nachos exits, so once the
	 * first TCB is created, this vector is basically never empty.
	 */
	private static Vector<TCB> runningThreads = new Vector<TCB>();

	private static Privilege privilege;
	private static KThread toBeDestroyed = null;

	/**
	 * <tt>true</tt> if and only if this TCB is the first TCB to start, the one
	 * started in <tt>Machine.main(String[])</tt>. Initialized by
	 * <tt>start(Runnable)</tt>, on the basis of whether <tt>currentTCB</tt> has
	 * been initialized.
	 */
	private boolean isFirstTCB;

	/**
	 * A reference to the Java thread bound to this TCB. It is initially
	 * <tt>null</tt>, assigned to a Java thread in <tt>start(Runnable)</tt>, and
	 * set to <tt>null</tt> again in <tt>destroy()</tt>.
	 */
	private Thread javaThread = null;

	/**
	 * <tt>true</tt> if and only if the Java thread bound to this TCB ought to
	 * be running. This is an entirely different condition from membership in
	 * <tt>runningThreads</tt>, which contains all TCB objects that have started
	 * and have not terminated. <tt>running</tt> is only <tt>true</tt> when the
	 * associated Java thread ought to run ASAP. When starting or destroying a
	 * TCB, this is temporarily true for a thread other than that of the current
	 * TCB.
	 */
	private boolean running = false;

	/**
	 * Set to <tt>true</tt> by <tt>destroy()</tt>, so that when
	 * <tt>waitForInterrupt()</tt> returns in the doomed TCB, <tt>yield()</tt>
	 * will know that the current TCB is doomed.
	 */
	private boolean done = false;

	private KThread nachosThread = null;
	private boolean associated = false;
	private Runnable target;
	private Runnable tcbTarget;

	private static class TCBPrivilege implements Privilege.TCBPrivilege {
		public void associateThread(KThread thread) {
			Lib.assertTrue(currentTCB != null);
			currentTCB.associateThread(thread);
		}

		public void authorizeDestroy(KThread thread) {
			TCB.authorizeDestroy(thread);
		}
	}
}
